Numerical Analysis (CS 450) Spring 2022
What | Where |
---|---|
Time/place | Wed/Fri 9:30am–10:45am 180 Bevier Hall / Catalog |
Class URL | https://relate.cs.illinois.edu/course/cs450-s22/ |
Recorded Lectures | https://mediaspace.illinois.edu/channel/cs450_s22 |
Quizzes
Older quizzes
- Quiz 21
- Quiz 20
- Quiz 19
- Quiz 18
- Quiz 17
- Quiz 16
- Quiz 15
- Quiz 14
- Quiz 13
- Quiz 12
- Quiz 11
- Quiz 10
- Quiz 9
- Quiz 8
- Quiz 7
- Quiz 6
- Quiz 5
- Quiz 4
- Quiz 3
- Quiz 2
- Quiz 1
Homework
Older homeworks
- Homework 11
- Homework 10
- Homework 9
- Homework 8
- Homework 7
- Homework 6
- Homework 5
- Homework 4
- Homework 3
- Homework 2
- Homework 1
4-Credit Hour Assignment
- Final Project Submit Final Project Here
- Homework 13 4-credit
- No Homework 12 4-credit: continue working on final project
Older 4-Credit Assignments
- Homework 10 4-credit
- Homework 9 4-credit
- Homework 8 4-credit
- Homework 7 4-credit
- Homework 6 4-credit
- Homework 5 4-credit
Exams
Please find information on our upcoming exam between Tuesday, Feb 15 and Thursday, Feb 17 on https://cbtf.illinois.edu/faculty/syllabus. Reserve your time slots in the CBTF as soon as possible--otherwise your preferred times may no longer be available.
You should login to https://cbtf.engr.illinois.edu/sched to automatically pick up a roster affiliation to your courses in the scheduler. That also makes sure the you get the reminder emails when new exams become available to reserve. It’s also good to get your DRES letters of accommodation on file early before you need them, instructions at https://cbtf.illinois.edu/students/dres
The student instructions section of https://cbtf.illinois.edu is good to review, it has guides for our policies, what to do if an exam is missed, how to get support, etc.
The topics of exam 1 will be:
* Chapter 1 (all material covered in lectures, HW, quizzes)
* Chapter 2 (all material covered in lectures, HW, quizzes)
* Chapter 3 (material covered up through Wednesday, Feb 9)
The topics of exam 2 will be:
* Chapter 3 (all material covered in lectures, HW, quizzes)
* Chapter 4 (all material covered in lectures, HW, quizzes)
* Chapter 5 (all material covered in lectures, HW, quizzes)
* Chapter 6 (all material covered in lectures, HW, quizzes)
Office Hours
Note that some office hours are held in-person and others are held online.
-
Review Session: time 7 PM – 9pm Zoom (Click to Join)
-
Paul Fischer: time WF 11:30 – 12:30pm Zoom (Click to Join)
- Nathanael: Wednesday 5:00 – 7:00, 207 Siebel Center
- Raul: Tues/Thurs 1:30pm – 2:30pm Zoom (Click to Join)
- Lukas: Mon/Tue 3pm – 4pm, Zoom (Click to join)
Course Outline
-
Introduction to Scientific Computing
- Notes for Chapter 1
- Round-Off Example: Finite Differences
- Notes for Chapter 2
- Notes for Chapter 3
- Notes for Chapter 4
- Notes for Chapter 5
- Notes for Chapter 6
- Notes for Chapter 7
- Notes for Chapter 8
- Notes for Chapter 9
- Notes for Chapter 10
- Notes for Chapter 11
- Some review notes
- About the Class
- Errors, Conditioning, Accuracy, Stability
- In-Class Activity: Forward/Backward Error
- Floating Point
- In-Class Activity: Floating Point
- Demo: Catastrophic Cancellation
- Demo: Conditioning of Evaluating tan
- Demo: Density of Floating Point Numbers
- Demo: Floating Point and the Series for the Exponential Function
- Demo: Floating Point vs Program Logic
- Demo: Floating point and the Harmonic Series
- Demo: Picking apart a floating point number
- Demo: Truncation vs Rounding
- Demo: Vector Norms
- Demo: Writing Testable Numerics Code
-
Systems of Linear Equations
- Theory: Conditioning
- In-Class Activity: Matrix Norms and Conditioning
- Methods to Solve Systems
- LU: Application and Implementation
- In-Class Activity: LU
- Demo: Coding back-substitution
- Demo: Complexity of Mat-Mat multiplication and LU
- Demo: Condition number visualized
- Demo: Conditioning of 2x2 Matrices
- Demo: LU Factorization with Partial Pivoting
- Demo: LU Factorization
- Demo: Matrix norms
- Demo: Sherman-Morrison
- Demo: Vanilla Gaussian Elimination
-
Linear Least Squares
- Introduction
- In-Class Activity: Least Squares
- Sensitivity and Conditioning
- Solving Least Squares
- In-Class Activity: QR
- In-Class Activity: Householder, Givens, SVD
- Demo: 3x3 Givens demo
- Demo: 3x3 Householder demo
- Demo: Gram-Schmidt and Modified Gram-Schmidt
- Demo: Gram-Schmidt--The Movie
- Demo: Image compression
- Demo: Interactive Polynomial Fit
- Demo: Issues with the normal equations
- Demo: Keeping track of coefficients in Gram-Schmidt
- Demo: Normal equations vs Pseudoinverse
- Demo: Polynomial fitting with the normal equations
- Demo: Relative cost of matrix factorizations
-
Eigenvalue Problems
- Properties and Transformations
- Sensitivity
- Computing Eigenvalues
- In-Class Activity: Eigenvalues
- Krylov Space Methods
- Demo: Arnoldi Iteration
- Demo: Bauer-Fike Eigenvalue Sensitivity Bound
- Demo: Computing the SVD
- Demo: Householder Similarity Transforms
- Demo: Orthogonal Iteration
- Demo: Power iteration and its Variants
- Demo: Rounding in characteristic polynomial using SymPy
-
Nonlinear Equations
- Introduction
- In-Class Activity: Krylov and Nonlinear Equations
- Iterative Procedures
- Methods in One Dimension
- In-Class Activity: Nonlinear Equations
- Methods in $n$ Dimensions (``Systems of Equations'')
- Demo: Bisection Method
- Demo: Convergence of Newton's Method
- Demo: Convergence of the Secant Method
- Demo: Fixed point iteration
- Demo: Newton's Method
- Demo: Newton's method in n dimensions
- Demo: Rates of Convergence
- Demo: Secant Method
- Demo: Three quadratic functions
-
Optimization
- Introduction
- In-Class Activity: Optimization Theory
- Methods for unconstrained opt. in one dimension
- In-Class Activity: Optimization Methods
- Methods for unconstrained opt. in $n$ dimensions
- Nonlinear Least Squares
- Constrained Optimization
- Demo: Conjugate Gradient Method
- Demo: Gauss-Newton
- Demo: Golden Section Proportions
- Demo: Nelder-Mead Method
- Demo: Newton's Method in 1D
- Demo: Newton's Method in n dimensions
- Demo: Sequential Quadratic Programming
- Demo: Steepest Descent
-
Interpolation
- Introduction
- Methods
- In-Class Activity: Interpolation
- Error Estimation
- Piecewise interpolation, Splines
- Demo: Chebyshev interpolation
- Demo: Choice of Nodes for Polynomial Interpolation
- Demo: Composite Gauss Interpolation Error
- Demo: Interpolation Error
- Demo: Interpolation with Radial Basis Functions
- Demo: Jump with Chebyshev Nodes
- Demo: Monomial interpolation
- Demo: Orthogonal Polynomials
- Demo: Playing with Barycentric Interpolation
-
Numerical Integration and Differentiation
- Numerical Integration
- Quadrature Methods
- Accuracy and Stability
- Gaussian Quadrature
- Composite Quadrature
- Numerical Differentiation
- Richardson Extrapolation
- In-Class Activity: Differentiation and Quadrature
- Demo: Accuracy of Newton-Cotes
- Demo: Finite Differences vs Noise
- Demo: Floating point vs Finite Differences
- Demo: Gaussian quadrature weight finder
- Demo: Newton-Cotes weight finder
- Demo: Richardson with Finite Differences
- Demo: Taking Derivatives with Vandermonde Matrices
-
Initial Value Problems for ODEs
- Existence, Uniqueness, Conditioning
- Numerical Methods (I)
- Accuracy and Stability
- Stiffness
- Numerical Methods (II)
- In-Class Activity: Initial Value Problems
- Demo: Backward Euler stability
- Demo: Dissipation in Runge-Kutta Methods
- Demo: Forward Euler stability
- Demo: Stability regions
- Demo: Stiffness
-
Boundary Value Problems for ODEs
- Existence, Uniqueness, Conditioning
- Numerical Methods
- Demo: Finite differences
- Demo: Shooting method
- Demo: Sparse matrices
- Partial Differential Equations and Sparse Linear Algebra
- Fast Fourier Transform
- Additional Topics
Team
Textbook
Michael T. Heath, Revised Second Edition, Society for Industrial and Applied Mathematics
Also see our class Piazza forum for a discount code for purchasing the book from SIAM.
Computing
We will be using Python with the libraries numpy, scipy and matplotlib for in-class work and assignments. No other languages are permitted. Python has a very gentle learning curve, so you should feel at home even if you've never done any work in Python.
Running Code on your Own Computer
While running code in this online system should technically suffice to do your work for this class, you may find it useful to also install Python on your own computer.
The recommended and perhaps one of the easier ways of doing so involves downloading the Anaconda Python distribution. Note that this is a commercial product (even if it is free of charge), and this is not intended as an endorsement of the company or the product. Note that we cannot promise to provide technical support for this installation.
Another way to obtain a Python installation is through a virtual machine image:
Grading Policies
Python Help
(see section 1 of the outline for more)
- Python tutorial
- Facts and myths about Python names and values
- Learn Python the hard way
- Project Euler (Lots of practice problems)
- From Python to Numpy
- PythonTutor (Execute Python step-by-step, with pictures)
Python workshop material
- Video: Located on Echo 360 along with the other class recordings
- Tutorial material
- Scipy lecture notes
- CSE workshop training material
Numpy Help
(see section 1 of the outline for more)
- Introduction to Python for Science
- The SciPy lectures
- The Numpy MedKit by Stéfan van der Walt
- The Numpy User Guide by Travis Oliphant
- Numpy/Scipy documentation
- More in this reddit thread
- An introduction to Numpy and SciPy